Then we call the kernel, the triple the signature, and the height of , respectively. We call a -number if it is a Carmichael number with each prime factor . If is a -number and a strong pseudoprime to the bases for , we call a -spsp . Since -numbers have probability of error (the upper bound of that for the Rabin-Miller test), they often serve as the exact values or upper bounds of (the smallest strong pseudoprime to all the first prime bases). If we know the exact value of , we will have, for integers , a deterministic efficient primality testing algorithm which is easy to implement.
In this paper, we first describe an algorithm for finding -spsp(2)'s, to a given limit, with heights bounded. There are in total -spsp's with heights . We then give an overview of the 21978 - spsp(2)'s and tabulate of them, which are -spsp's to the first prime bases up to ; three numbers are spsp's to the first 11 prime bases up to 31. No -spsp's to the first prime bases with heights were found. We conjecture that there exist no -spsp's to the first prime bases with heights and so that
which was found by the author in an earlier paper. We give reasons to support the conjecture. The main idea of our method for finding those -spsp's is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates of -spsp's and their prime factors to Miller's tests, and obtain the desired numbers. At last we speed our algorithm for finding larger -spsp's, say up to , with a given signature to more prime bases. Comparisons of effectiveness with Arnault's and our previous methods for finding -strong pseudoprimes to the first several prime bases are given.
In this paper, we first follow the first author's previous work to use biquadratic residue characters and cubic residue characters as main tools to tabulate all strong pseudoprimes (spsp's) to the first five or six prime bases, which have the form with odd primes and ; then we tabulate all Carmichael numbers , to the first six prime bases up to 13, which have the form with each prime factor . There are in total 36 such Carmichael numbers, 12 numbers of which are also spsp's to base 17; 5 numbers are spsp's to bases 17 and 19; one number is an spsp to the first 11 prime bases up to 31. As a result the upper bounds for and are lowered from 20- and 22-decimal-digit numbers to a 19-decimal-digit number:
We conjecture that
and give reasons to support this conjecture. The main idea for finding these Carmichael numbers is that we loop on the largest prime factor and propose necessary conditions on to be a strong pseudoprime to the first prime bases. Comparisons of effectiveness with Arnault's, Bleichenbacher's, Jaeschke's, and Pinch's methods for finding (Carmichael) numbers with three prime factors, which are strong pseudoprimes to the first several prime bases, are given.
We show that there is only one embedding of in at the prime , up to self-maps of . We also describe the effect of the group of self-equivalences of at the prime on this embedding and then show that the Friedlander exceptional isogeny composed with a suitable Adams map is an involution of whose homotopy fixed point set coincide with